package airthmetic.exercise.stack;

import java.util.Stack;

// 单调栈
public class MonotonicityStack {


    /**
     * 给定一个数组,返回同等代表源数组中每个元素左边第一个小于自己的数的数组,构造单调递减栈,如果左边
     没有小于自己的返回-1
     * @param nums
     * @return int[]
     * 单调递减栈
     */
    public static int[] getLeftMinNum(int[] nums){
        int[] res = new int[nums.length];
        Stack<Integer> stack = new Stack<>();

        for (int i=0; i< nums.length; i++){
            while(!stack.isEmpty() && stack.peek() >= nums[i]){
                stack.pop();
            }

            if(stack.isEmpty()){
                res[i] = -1;
            }else{
                res[i] = stack.peek();
            }
            stack.push(nums[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{6,10,3,7,4,4,12,5};
        int[] res = getLeftMinNum(nums);
        for (int re : res) {
            System.out.println(re);
        }
    }

}
